package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/18 18:08
 */
public class LIS {
    public int[] LIS(int[] arr) {
        // write code here
        int[] nums = new int[arr.length]; // 存储对应位置所在arr[i]中的下标
        int[] temp = new int[arr.length]; // temp的长度就是最大递增子序列的长度, 但不是正确答案
        nums[0] = 1;
        int tempIndex = 0;
        temp[tempIndex] = arr[0];
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] > temp[tempIndex]) { // 如果当前元素比可以作为最大递增自序列的下一个元素, 加入temp中
                ++tempIndex;
                nums[i] = tempIndex + 1;
                temp[tempIndex] = arr[i];
            } else {
                // 如果比当前最大递增自序列的最后一个元素小, 就在temp数组里找第一个>=当前元素的值并替换
                int l = 0, r = tempIndex;
                while (l <= r) {
                    int mid = (r + l) / 2;
                    if (arr[mid] >= temp[tempIndex]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                temp[l] = arr[i];
                nums[i] = l + 1;
            }
        }
        // 结果数组, 大小就是temp的大小
        int[] res = new int[tempIndex + 1];
        // 因为要按字典序排序, 所以从后往前遍历更好找到答案
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == tempIndex + 1) {
                res[tempIndex] = arr[i];
                --tempIndex;
            }
        }
        return res;
    }
}
